package a00_LeetCode.Tree;

/**
 * @Author quan
 * @Description 另一棵树的子树
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 * @Date 2023/3/24 19:21
 */
public class Num572_isSubtree {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //(1)两个树都为null，返回T
        if(root==null && subRoot==null){
            return true;
        }
        //(2)两个树有一个为null，返回F
        if(root==null || subRoot==null){
            return false;
        }
        //(3)走到这里，则说明两个树的根都不为null,说明两个树都有根节点
        // 此时判断两个树的是否是相同的树，包含结构相同和值相同
        if (isSameTree(root,subRoot)) {
            return true;
        }
        // 走到这里说明根节点的值和结构是相同的，此时判断以root为根的左子树或者右子树中是否包含subRoot为根的树----->注意这里是包含关系，不是相等
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
    //传入两个树的根节点，判断两个树是否为相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1.base case
        if (p == null && q == null) {
            return true;
        }
        // 一个是空树一个非空
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        // 继续判断左子树和右子树是否相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

